package dmsxl.erchashu;

import java.util.*;

/**
 * Author: Zhang Dongwei
 * Date: 2023/5/5 16:44
 * 二叉树的层序遍历
 */
public class ecs5_102 {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(9);
        TreeNode node3 = new TreeNode(20);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        List<List<Integer>> lists = levelOrder(node1);
        System.out.println(lists);
    }

//    public static List<List<Integer>> res = new ArrayList<>();

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
//        checkFun(root, 0);
//        checkFun1(root);
        if (root == null) return null;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int len = que.size();

            while (len > 0){
                TreeNode temNode = que.poll();
                list.add(temNode.val);

                if (temNode.left != null) que.offer(temNode.left);
                if (temNode.right != null) que.offer(temNode.right);
                len --;
            }
            res.add(list);
        }

        return res;
    }

//    public static void checkFun(TreeNode node, int deep){
//        if (node == null) return;
//        deep ++;
//
//        if (res.size() < deep){
//            List<Integer> item = new ArrayList<>();
//            res.add(item);
//        }
//        res.get(deep - 1).add(node.val);
//        checkFun(node.left, deep);
//        checkFun(node.right, deep);
//    }

//    public static void checkFun1(TreeNode node){
//        if (node == null) return;
//        Queue<TreeNode> que = new LinkedList<>();
//        que.offer(node);
//
//        while (!que.isEmpty()){
//            ArrayList<Integer> list = new ArrayList<>();
//            int len = que.size();
//
//            while (len > 0){
//                TreeNode temNode = que.poll();
//                list.add(temNode.val);
//
//                if (temNode.left != null) que.offer(temNode.left);
//                if (temNode.right != null) que.offer(temNode.right);
//                len --;
//            }
//            res.add(list);
//        }
//    }
}
